DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2022.1

An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles

Authors: Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract

The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A* heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.

Cite as

Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas. An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2022.1,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Maristany de las Casas, Pedro},
  title =	{{An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.1},
  URN =		{urn:nbn:de:0030-drops-171052},
  doi =		{10.4230/OASIcs.ATMOS.2022.1},
  annote =	{Keywords: shortest path problem, a-star algorithm, flight trajectory optimization, flight planning, heuristics}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2021.7

Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data

Authors: Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.

Cite as

Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe. Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.7,
  author =	{Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine},
  title =	{{Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{7:1--7:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.7},
  URN =		{urn:nbn:de:0030-drops-148767},
  doi =		{10.4230/OASIcs.ATMOS.2021.7},
  annote =	{Keywords: Preprocessing Shortest Path Problems, Interval Data, Graph Algorithms}
}

Search Results

Documents authored by Maristany de las Casas, Pedro

An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles

Abstract

Cite as

Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data

Abstract

Cite as

Thanks for your feedback!

Could not send message